package strings;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/3/4
 * @verdion 1.0.0
 * 给定一个形如 “HH:MM” 表示的时刻，利用当前出现过的数字构造下一个距离当前时间最近的时刻。每个出现数字都可以被无限次使用。
 *
 * 你可以认为给定的字符串一定是合法的。例如，“01:34” 和 “12:09” 是合法的，“1:34” 和 “12:9” 是不合法的。
 *
 *  
 *
 * 样例 1:
 *
 * 输入: "19:34"
 * 输出: "19:39"
 * 解释: 利用数字 1, 9, 3, 4 构造出来的最近时刻是 19:39，是 5 分钟之后。结果不是 19:33 因为这个时刻是 23 小时 59 分钟之后。
 *  
 *
 * 样例 2:
 *
 * 输入: "23:59"
 * 输出: "22:22"
 * 解释: 利用数字 2, 3, 5, 9 构造出来的最近时刻是 22:22。 答案一定是第二天的某一时刻，所以选择可构造的最小时刻。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-closest-time
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NextClosestTime {
    Set<Integer> hours = new HashSet<>();
    Set<Integer> mins = new HashSet<>();
    public String nextClosestTime(String time) {
        if(time == null || time.length() != 5){
            return "";
        }
        int[] nums = new int[4];
        int i = 0;
        for(char c: time.toCharArray()){
            if(c != ':'){
                nums[i] = c - '0';
                i++;
            }
        }
        int cur = nums[0] * 1000 + nums[1] * 100 + nums[2]*10 + nums[3];

        build(nums, 10, 0);
        List<Integer> times = new ArrayList<>();
        for(Integer h: hours){
            for(Integer m: mins){
                times.add(h * 100 + m);
            }
        }
        Collections.sort(times);
        int t = 0;
        for(; t< times.size(); t ++){
            if(times.get(t) == cur){
                break;
            }
        }
        t = (t + 1) % times.size();
        int next = times.get(t);
        StringBuilder builder = new StringBuilder();
        int tmp = 1000;
        while(tmp > 0){
            if(tmp == 10){
                builder.append(":");
            }
            if(next < tmp){
                builder.append("0");
            } else {
                int n = next /tmp;
                builder.append(n);
                next %= tmp;
            }
            tmp /= 10;
        }
        return builder.toString();
    }

    private void build(int[] nums, int pos, int num){
        if(pos == 0){
            if(num <= 23){
                hours.add(num);
            }
            if(num <= 59){
                mins.add(num);
            }
            return;
        }
        for(int i = 0; i < nums.length; i ++){
            int n = nums[i] * pos;
            build(nums, pos/10, n + num);
        }
    }

    public static void main(String[] args){
        System.out.println((new NextClosestTime()).nextClosestTime("19:34"));
    }
}
